package 力扣91;

import java.awt.*;

/**
 * @ClassName : Day9_109_有序链表转换二叉搜索树
 * @Author : 骆发茂
 * @Date: 2021/12/20 9:56
 * @Description : https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
 */
public class Day9_109_有序链表转换二叉搜索树 {
    class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            if (head == null) {
                return null;
            }
            if (head.next == null) {
                return new TreeNode(head.val);
            }
            //快慢指针找中点
            /*pre指向中点前一个
            * slow指向中点
            * */
            ListNode fast = head, slow = head,pre=null;
            while (fast!=null&&fast.next!=null){
                fast = fast.next.next;
                pre = slow;
                slow = slow.next;

            }
            pre.next = null;

            ListNode rightList = slow.next;
                //中点
            TreeNode root = new TreeNode(slow.val);
                /*左子树*/
            root.left = sortedListToBST(head);
                /*右子树*/
            root.right = sortedListToBST(rightList);
            return root;
        }
    }
}